% -*- coding:utf-8 -*-

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}

\usepackage[bookmarks, hyperfootnotes=false, colorlinks=true,%
            urlcolor=blue, linkcolor=black,  citecolor=black,%
            pagecolor=black, anchorcolor=black, breaklinks=true]{hyperref}

\usepackage{enumerate}
\usepackage{eurosym}
\usepackage{graphicx}
\usepackage{times}
\usepackage{color}
\usepackage{array}
\usepackage{colortbl}
\usepackage{longtable}

\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{hyperref}
\usepackage{tikz}

\usepackage{epsfig}
\usepackage{float}
\usepackage{amsmath}
\usepackage{lscape}

\setlength{\headheight}{16pt}
\setlength{\oddsidemargin}{17pt}
\setlength{\textwidth}{420pt}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{600pt}
\setlength{\marginparwidth}{55pt}


\newcommand{\fsm}{\emph{FSM}}
\newcommand{\ice}{\emph{ICE}}
\newcommand{\icefield}{\emph{IceField}}
\newcommand{\slice}{\emph{Slice}}

\pagestyle{fancy}

\renewcommand{\footrulewidth}{0.5pt}

\fancyhead[R]{Práctica 1-Tarea 2}
\fancyhead[L]{Inteligencia Artificial}
\fancyfoot[R]{Manuel J. Abaldea Gª-Pliego}
\fancyfoot[L]{Test de la estructura de datos}


\newenvironment{float_code} {
      \begin{lst}
      }
      {
      \end{lst}
      }


\newfloat{lst}{H}{lop}[section]
\floatname{lst}{Listado}
\floatplacement{codigo}{!htb}
\floatstyle{plain}


\begin{document}

\begin{center}
\begin{Large}\textit{\textquotedblleft
Inteligencia Artificial \ \ Práctica 1
\textquotedblright}\end{Large}
\end{center}

\vspace*{0.5cm}

\begin{flushleft}
\begin{large}
\textit{
Alumno: Manuel J. Abaldea Gª-Pliego
}
\end{large}
\end{flushleft}

\vspace*{1cm}

\section*{Tarea 1: Tecnologías utilizadas y definición de estado y acción}
\subsection*{Tecnologías utilizadas y definición de estado y acción.}
\subsubsection*{Tecnologías usadas}
Para la realización de esta primera práctica utilizaré el lenguaje de
programación \emph{C++}.

\emph{C++} nos proporciona varias ventajas como
que es un lenguaje orientado a objetos, esto facilita la creación de
sistemas complejos proporcionando robustez y legibilidad en el
código. ¿Por qué no utilizar otro lenguaje orientado a objetos como
\emph{Java}? Por didáctica, he trabajado mucho menos con \emph{C++} y
quiero aprovechar este trabajo para practicar. Otra gran ventaja, que
se puede volver en mi contra, es el manejo de punteros y memoria; esto
nos proporciona un mejor control de la memoria y administración de los
recursos pero puede complicar el código si no se tiene suficiente
experiencia. También están las típicas ventajas de: es muy utilizado
y hay muchos tutoriales, existen muchas librerías, es compatible con
las de C, etc.

Para manipular las imágenes utilizaré una librería propia. Guardando
la imagen como \emph{PGM} en \emph{ASCI} puedo tomar la imagen como un
texto plano y trabajar con ella, de modo que una librería simple que
lea las cadenas de texto y obtenga la información necesaria para
trabajar es suficiente. Esto dará simplicidad a la práctica y bien
programada puede incluso ahorrar recursos.

\subsubsection*{Problema de espacio de estados simple.}
Para definir un estados utilizaremos:
\begin{itemize}
\item posición: en el eje X e Y
\end{itemize}

De modo que un estado sería: $\{X,Y\}$

Los actuadores serían los movimientos, considerando que comenzamos
desde la esquina superior izquierda:
\begin{itemize}
\item mover izquierda: X-1
\item mover derecha: X+1
\item mover abajo: Y+1
\item mover arriba: Y-1
\end{itemize}

\clearpage

El motivo de comenzar desde la esquina superior izquierda es que
utilizaré una matriz de enteros para representar el mapa, de modo que
de este modo las coordenadas X e Y coincidirán con las coordenadas de
la matriz, y el valor en dicha coordenada será el coste en escala de
grises (0-15) de la posición.
Antes de que los actuadores transformen el estado tendremos en cuenta:
\begin{itemize}
\item mover izquierda: solo si X-1 > 0
\item mover derecha: solo si X+1 < anchura del mapa
\item mover abajo: solo si Y+1 < profundidad del mapa
\item mover arriba: solo si Y-1 > 0
\end{itemize}

Para el almacenamiento de los datos durante la ejecución utilizaré una
base de datos \emph{SQLite}. La utilicé el año pasado y aunque es algo
más complejo de utilizar que otra estructura de datos intrínseca en el
código como una cola circular o un árbol, me proporciona rubustez
(aguanta millones de nodos sin despeinarse) y me facilitará la gestión
(creación, acceso, modificación, eliminación) de los nodos así como la
gestión de la memoria.

\subsubsection*{Estructuras necesarias.}
Será necesario un árbol con los nodos de nuestro problema y una cola
con prioridad que será la frontera.
En nuestra implementación no será necesario tener las estructuras tal
cual, con un buen manejo de las instrucciones SQL se puede trabajar
con la base de datos como si fuese cualquiera de las dos estructuras
mencionadas. Por ejemplo, para almacenar la frontera, como si una cola
con prioridad se refiriese, crearemos los nodos del siguiente modo:
\begin{verbatim}
CREATE TABLE nodes(
       iden integer primary key,
       coX integer,
       coY integer,
       cost integer,
       father integer);
\end{verbatim}

de modo que la prioridad podrá venir dada por el coste, o por el tipo
de búsqueda según la orden SQL a ejecutar. Ejemplos:
\begin{verbatim}
Para búsqueda en anchura:
  SELECT * FORM nodes WHERE iden = (select min(iden) from nodes);
Para búsqueda en profundidad:
  SELECT * FORM nodes WHERE iden = (select max(iden) from nodes);
Para costo:
  SELECT * FORM nodes WHERE iden = (select min(cost) from nodes);
\end{verbatim}

Durante la ejecución del programa, en el proceso de búsqueda, la {\bf
  paginación en memoria} está pensada de modo que toda la frontera
esté almacenada en disco duro mediante la base de datos y en memoria
principal tan solo se tenga durante ejecución el nodo actual sobre el
que se esté trabajando. El resto del proceso que no sea referente a la
búsqueda (extraer datos del mapa, pintar solución, gestión de tiempo
transcurrido, etc) serán tratados directamente en memoria principal
mediante registros, ya que el espacio que utilizarán será ínfimo en
comparación con el necesario para desarrollar la búsqueda.




\section*{Tarea 2: Test de la estructura de datos}
\subsection*{Estructura de datos para la cola con prioridad}
La estructura de datos para nuestra base de datos será la siguiente:
\begin{verbatim}
CREATE TABLE nodes(
             iden integer primary key,
             coX integer,
             coY integer,
             cost integer,
             prof integer,
             father integer,
             f integer);
\end{verbatim}


\subsection*{Evaluar la capacidad de la estructura}
Respecto al número máximo de nodos con los que podemos trabajar, las
especificaciones de \emph{SQLite} en la versión 3 (base de datos con
la que se trabajará) el tamaño máximo teórico de la base de datos
sería de 2 TeraBytes, pero se especifica que en la práctica no es
aconsejable utilizar bases de datos mayores de 100 GigaBytes.
Teniendo en cuenta que las estructuras probadas han generado con 1
millón de nodos una base de datos de 22,4 MegaBytes se estima que la
estructura funcionaría perfectamente hasta 4500 millones de nodos
(100 GigaBytes) y podría llegar a colapsar (teóricamente) a los 90000
millones de nodos, pero necesitaríamos un disco duro con 2 TeraBytes
libres.

Algunos tiempos de escritura obtenidos han sido los siguientes:
\begin{itemize}
\item 1000 nodos 76.1303 segundos
\item 101000 nodos 7515.1348 segundos
\item 1000000 nodos 69818.5171 segundos
\item 10000000 nodos 701131.06244 segundos
\end{itemize}

Tiempo medio de inserción de un nodo: 0,0744 segundos. Se debe tener
en cuenta que estos tiempos ha sido obtenidos en un Pentium4 con
3GigaBytes de RAM.

\clearpage

\subsection*{Algoritmo de búsqueda de soluciones}
Se interpreta que el algoritmo devuelve un vector con los
identificadores de los nodos que componen la solución. Si existe un
único nodo con identificador 0 significará que no se ha encontrado
solución.

\begin{verbatim}
int* Busqueda (mapa_problema){
     frontera = Frontera(mapa_problema);   //nodo inicial
     while front.lenght > 0{
          nodo_actual = frontera.pop();    //extraer y eliminar nodo
          if nodo_actual.coordX = MAX_W and nodo_actual.coordY = MAX_D{
               sol_nodo = nodo_actual;
               break;
          }
          nodo_actual.expand(frontera);
     }
     if sol_nodo == NULL
          return 0;
     else
          return CrearSol(sol_nodo)
\end{verbatim}

\section*{Código implementado}
El código, así como el seguimiento de esta práctica está disponible en:

\url{https://code.google.com/p/ia-2012-13/}

\end{document}
